use std::collections::{BinaryHeap, HashMap};
use crate::solution::Solution;

impl Solution {
    pub fn min_set_size(arr: Vec<i32>) -> i32 {
        let mut count_map=HashMap::new();
        let mut ans=0;
        let mut half =(arr.len() / 2) as i32;
        arr.iter().for_each(|&x| {
            count_map.entry(x).and_modify(|v| *v += 1).or_insert(1);
        });
        let mut heap=BinaryHeap::from_iter(count_map.values());
       while let Some(&key) = heap.pop() {
           half-=key;
           ans+=1;
           if half<=0{
               break
           }
       }
        if ans==0{
            1
        }else{
            ans
        }

    }
}